{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Substrings With Fixed Ratio"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fixedRatio"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #固定比率的子字符串数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制字符串 <code>s</code>&nbsp;和两个整数 <code>num1</code> 和 <code>num2</code>。<code>num1</code> 和 <code>num2</code> 为互质。</p>\n",
    "\n",
    "<p><strong>比率子串&nbsp;</strong>是 s 的子串，其中子串中 <code>0</code> 的数量与 <code>1</code>&nbsp;的数量之比正好是&nbsp;<code>num1 : num2</code>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>num1 = 2</code>&nbsp;和 <code>num2 = 3</code>，那么 <code>\"01011\"</code>&nbsp;和 <code>\"1110000111\"</code>&nbsp;是比率子串，而 <code>\"11000\"</code>&nbsp;不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em><code>s</code> 的&nbsp;<strong>非空&nbsp;</strong>比率子串的个数。</em></p>\n",
    "\n",
    "<p><b>注意</b>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>子串&nbsp;</strong>是字符串中连续的字符序列。</li>\n",
    "\t<li>如果 <code>gcd(x, y) == 1</code>，则 <code>x</code> 和 <code>y</code> 为&nbsp;<strong>互质</strong>，其中 <code>gcd(x, y)</code>&nbsp;为 <code>x</code>&nbsp;和 <code>y</code> 的最大公约数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"0110011\", num1 = 1, num2 = 2\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 有 4 个非空的比率子串。\n",
    "- 子字符串 s[0..2]: \"<u>011</u>0011\"。它包含一个 0 和两个 1。比例是 1:2。\n",
    "- 子字符串 s[1..4]: \"0<u>110</u>011\"。它包含一个 0 和两个 1。比例是 1:2。\n",
    "- 子字符串 s[4..6]: \"0110<u>011</u>\"。它包含一个 0 和两个 1。比例是 1:2。\n",
    "- 子字符串 s[1..6]: \"0<u>110011</u>\"。它包含两个 0 和四个 1。比例是 2:4 == 1:2。\n",
    "它可以显示没有更多的比率子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"10101\", num1 = 3, num2 = 1\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> s 没有比率子串，返回 0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= num1, num2 &lt;= s.length</code></li>\n",
    "\t<li><code>num1</code> 和&nbsp;<code>num2</code> 互质。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-substrings-with-fixed-ratio](https://leetcode.cn/problems/number-of-substrings-with-fixed-ratio/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-substrings-with-fixed-ratio](https://leetcode.cn/problems/number-of-substrings-with-fixed-ratio/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"0110011\"\\n1\\n2', '\"10101\"\\n3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def fixedRatio(self, s, num1, num2):\n",
    "        d, res, one, zero = defaultdict(int), 0, 0, 0\n",
    "        d[0] = 1\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                one += 1\n",
    "            else:\n",
    "                zero += 1\n",
    "            res += d[num1 * one - num2 * zero]\n",
    "            d[num1 * one - num2 * zero] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        dict = defaultdict(int)\n",
    "        dict[0] = 1\n",
    "        one = 0\n",
    "        zero = 0\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                one += 1\n",
    "            else:\n",
    "                zero += 1\n",
    "            temp = num1 * one - num2 * zero\n",
    "            res += dict[temp]\n",
    "            dict[temp] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        pre = defaultdict(int)\n",
    "        pre[0] = 1\n",
    "        zeros = ones = 0\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                ones += 1\n",
    "            else:\n",
    "                zeros += 1\n",
    "\n",
    "            pre_idx = num1 * ones - num2 * zeros\n",
    "            ans += pre[pre_idx]\n",
    "            pre[pre_idx] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和计数\n",
    "    # LC的老套路了,遍历字符串同时记录'0'和'1'的数量(记为zero,one),由于要求子串中'0'的数量比'1'的数量等于num1比num2,化简发现只需要当前num1 * one - num2 * zero值与之前某个前缀字符串的值相等,一边统计一边遍历即可 时间复杂度:O(n)\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        dct = defaultdict(int)\n",
    "        dct[0], one, zero, res = 1, 0, 0, 0\n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                one += 1\n",
    "            else:\n",
    "                zero += 1\n",
    "\n",
    "            pre = num1 * one - num2 * zero\n",
    "            res += dct[pre]\n",
    "            dct[pre] += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和计数\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        dct = defaultdict(int)\n",
    "        dct[0], one, zero, res = 1, 0, 0, 0\n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                one += 1\n",
    "            else:\n",
    "                zero += 1\n",
    "\n",
    "            tep = num1 * one - num2 * zero\n",
    "            res += dct[tep]\n",
    "            dct[tep] += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        dic = defaultdict(lambda:0)\n",
    "        dic[0] = 1\n",
    "        res = zero = one = 0\n",
    "        for n in s:\n",
    "            if n == '0':\n",
    "                zero += 1\n",
    "            else:\n",
    "                one += 1\n",
    "            res += dic[num1*one-num2*zero]\n",
    "            dic[num1*one-num2*zero] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        pre = defaultdict(int)\n",
    "        pre[0] = 1\n",
    "        zeros = ones = 0\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                ones += 1\n",
    "            else:\n",
    "                zeros += 1\n",
    "\n",
    "            pre_idx = num1 * ones - num2 * zeros\n",
    "            ans += pre[pre_idx]\n",
    "            pre[pre_idx] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        dc = defaultdict(int)\n",
    "        dc[0], one, zero, res = 1, 0, 0, 0\n",
    "        for i in s:\n",
    "            if i == '1': one += 1\n",
    "            else: zero += 1\n",
    "            tep = num1 * one - num2 * zero\n",
    "            res += dc[tep]\n",
    "            dc[tep] += 1\n",
    "        return res\n",
    "        \n",
    "    def fixedRatio2(self, s: str, num1: int, num2: int) -> int:\n",
    "        pre = defaultdict(int)\n",
    "        pre[0] = 1\n",
    "        one,zero = 0,0\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                one += 1\n",
    "            else:\n",
    "                zero += 1\n",
    "            ans += pre[num1 * one - num2 * zero]\n",
    "            pre[num1 * one - num2 * zero] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fixedRatio(self, s: str, num1: int, num2: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param s:\n",
    "        :param num1:\n",
    "        :param num2:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dp = defaultdict(int)\n",
    "        dp[0] = 1\n",
    "        n1, n2 = 0, 0\n",
    "        cnt = 0\n",
    "        for k, v in enumerate(s):\n",
    "            if v == \"0\":\n",
    "                n1 += 1\n",
    "            else:\n",
    "                n2 += 1\n",
    "            cnt += dp[n1*num2 - n2*num1]\n",
    "            dp[n1*num2 - n2*num1] += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fixedRatio(self, s: str, num0: int, num1: int) -> int:\n",
    "        temp0,temp1=0,0\n",
    "        k=num0/num1\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        d=defaultdict(int)\n",
    "        d[0]=1\n",
    "        for i in range(n):\n",
    "            if s[i]=='0':\n",
    "                temp0+=1\n",
    "            else :\n",
    "                temp1+=1\n",
    "            ans+=d[temp0*num1-temp1*num0]\n",
    "            d[temp0*num1-temp1*num0]+=1\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
